package com.zklh.leetcode.constructor.lru;


/**
 * 双向链表
 *
 * @author 坐看落花
 * @version 1.0
 * @date 2021/6/13 10:14
 */
public class DoubleList {
    // 头尾指针, 这里定义头尾指针为哨兵
    private Node head,tail;
    private int size;


    public DoubleList() {
        size = 0;
        head = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 插入头指针
     * @param node
     */
    public void addFirst(Node node) {
        Node tempNode = head.next;
        head.next = node;
        node.pre = head;
        node.next = tempNode;
        tempNode.pre = node;
        size++;
    }

    /**
     * 移除节点
     * @param node
     */
    public void remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        size--;
    }

    /**
     * 移除末尾节点
     * @return
     */
    public Node removeLast() {
        Node last = tail.pre;
        remove(last);
        return last;
    }

    public int getSize() {
        return size;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Node temp = head;
        while (temp != null) {
            sb.append(temp.key +","+temp.val+"|");
            temp = temp.next;
        }
        return sb.toString();
    }
}
